package LeetcodeTest_thirteen;
//括号生成
import java.util.ArrayList;
import java.util.List;

public class generateParenthesis
{
    public static void main(String[] args)
    {
        List<String> result=new ArrayList<String>();
        result=solution.generateParenthesis(3);
        for(int i=0;i<result.size();i++)
            System.out.println(result.get(i));
    }
}

class solution
{
    public static List<String> generateParenthesis(int n) {
        if(n==0)
            return null;
        ArrayList<String> answer = new ArrayList();
        StringBuilder result=new StringBuilder();
        leftORright(answer, result, 0, 0, n);
        return answer;
    }
    public static void leftORright(List<String> answer, StringBuilder result, int count_left, int count_right, int n){
        if (result.length() == 2*n)
            answer.add(result.toString());
        else
        {
            if (count_left < n)
            {
                result.append('(');
                leftORright(answer, result, count_left+1, count_right, n);
                result.deleteCharAt(result.length()-1);
            }
            if (count_right < count_left)
            {
                result.append(')');
                leftORright(answer, result, count_left, count_right+1, n);
                result.deleteCharAt(result.length() - 1);
            }
        }
    }
}